package linkedlist.other;

import linkedlist.Node;
import linkedlist.create.RecursionLinkedCreator;

import java.util.Arrays;

/**
 * @Author wangtengyu
 * @Create 2018-09-04-15:35 查找链表的中间节点
 */
public class FindMiddleNode {

  /**
   * 共遍历两次的方法 第一种方法，遍历一次，记录链表中节点的个数，遍历第二次，取得中间的值
   */
  public Node findMiddleNode(Node head) {
    double count = 0;
    double num = 0;
    //定义第二次遍历时的头节点
    Node midNode = head;

    //计数
    Node countNode = head;
    while (countNode != null) {
      countNode = countNode.getNext();
      count++;
    }

    //计算中间数值
    double mid = Math.ceil(count / 2);

    while (midNode != null) {
      num++;
      if (num == mid) {
        break;
      }
      midNode = midNode.getNext();
    }

    return midNode;
  }

  /**
   * 定义两个指针 slow每次前进1，fast，每次前进2。当fast指针读取不到数据的时候，slow指针所指的就是中间节点
   */
  public Node findMiddleNode2(Node head) {
    Node slow = head;
    Node fast = head;

    while (fast != null && fast.getNext() != null) {
      fast = fast.getNext().getNext();
      slow = slow.getNext();
    }
    return slow;
  }


  public static void main(String[] args) {
    RecursionLinkedCreator creator = new RecursionLinkedCreator();
    FindMiddleNode findMiddleNode = new FindMiddleNode();
    Node node = creator.createlinkedList(Arrays.asList(1, 2, 3, 4, 5));
    Node midNode = findMiddleNode.findMiddleNode(node);
//        Node midNode=findMiddleNode.findMiddleNode2(node);
    if (midNode == null) {
      System.out.println("列表为空，未找到中间节点");
    } else {
      System.out.println(midNode.getData());
    }


  }
}
